package org.example.Monotone_stack;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.LinkedList;

public class Daily_temperature {
    public static void main(String[] args) {
        //每日温度

        //给定一个整数数组 temperatures ，表示每天的温度，
        // 返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
        int[] t = {73,74,75,71,69,72,76,73};
        int[] ints = dailyTemperatures(t);
        System.out.println(Arrays.toString(ints));
    }
    //单调栈
    public static int[] dailyTemperatures(int[] temperatures) {
        LinkedList<Integer> linkedList = new LinkedList<>();
        int[] res = new int[temperatures.length];
        linkedList.add(0);
        for (int i = 1; i < temperatures.length; i++) {
            if (temperatures[i] <= temperatures[i-1]){
                linkedList.add(i);
            }else {
                while(linkedList.size() > 0 && temperatures[i] > temperatures[linkedList.getLast()]){
                    Integer index = linkedList.removeLast();
                    res[index] = i - index;
                }
                linkedList.add(i);
            }
        }
        return res;
    }
    //暴力超时
    public static int[] dailyTemperatures2(int[] temperatures) {
        int[] dp = new int[temperatures.length];
        for (int i = 0; i < temperatures.length; i++) {
            for (int j = i+1; j < temperatures.length; j++) {
                if (temperatures[j] > temperatures[i]){
                    dp[i] = j - i;
                    break;
                }
            }
        }
        return dp;
    }
}
